package 链表;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/copy-list-with-random-pointer/
 */
public class _138_复制带随机指针的链表 {

    Map<Node, Node> cache = new HashMap<>();
    /**
     * 回溯法 + 哈希表
     * @param head 目标链表
     * @return Node
     */
    public Node copyRandomListByMap(Node head) {
        if (head == null) {
            return null;
        }
        // 判断缓存区中是否存在节点，这一点主要是针对random节点，如果存在了该节点 返回给新节点的random
        if (!cache.containsKey(head)) {
            Node headNew = new Node(head.val);
            // 将节点和复制的节点存入Map缓存
            cache.put(head, headNew);
            // 递归将head.next 和 newHead.next映射上
            headNew.next = copyRandomListByMap(head.next);
            // 将head.random 和 newHead.random映射上
            headNew.random = copyRandomListByMap(head.random);
        }
        return cache.get(head);
    }

    /**
     * 迭代 + 节点拆分
     * @param head 目标链表
     * @return Node
     */
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        // 目的是为了将A‘ B’ C‘ 放到A B C 节点的后边 A->B->C 变为 A -> A' -> B -> B' -> C -> C'
        for (Node node = head; node != null; node = node.next.next) {
            Node newNode = new Node(node.val);
            newNode.next = node.next;
            node.next = newNode;
        }
        // 目的是为了让random指向于复制后的节点  例如  A.random -> B   A'.random -> B'
        for (Node node = head; node != null; node = node.next.next) {
            Node newNode = node.next;
            newNode.random = node.random != null ? node.random.next : null;
        }
        // 目的是为了让复制后的节点脱离原来的链表，让复制的节点相连
        Node ret = head.next;
        for (Node node = head; node != null; node = node.next) {
            Node newNode = node.next;
            node.next = newNode.next;
            newNode.next = newNode.next != null ? newNode.next.next : null;
        }
        return ret;
    }
}
